package Upr;

import java.util.Arrays;

public class MyQuickSort {

	public static void main(String[] args) {
		
		//int[] array = {6,67,4,3,4,7,8,4,4,5,677,2,11,43,35,6,7,4,2};
		int[] array = {45,98,4,3,87,6,5,7,1,6,8,7,89,8,65,5,78,5,9,3,45,2,7};
		System.out.println(Arrays.toString(array));
		quickSort(array, 0, array.length-1);
		System.out.println(Arrays.toString(array));
		
	}
	
	//left = first index of element
	//right = last index of element
	public static int partition(int[] array, int start, int end)
	{
	
		//int pivotInd = (int)Math.random()*(end-start) + start;
		int pivot = array[start];
		int storeIndex = start+1;
		for(int i = storeIndex; i <= end; i++)
		{
			System.out.println(Arrays.toString(array));
			if(array[i] < pivot)
			{
				swap(array, i, storeIndex);
				storeIndex++;
			}
		}
		swap(array, start, storeIndex-1);
		return storeIndex-1;//return the index where the pivot is.
	}
	
	public static void quickSort(int[] array, int start, int end)
	{
		if(start>end)
			return;
		else
		{
			int storeIndex = partition(array, start, end);
			quickSort(array, start, storeIndex-1);
			quickSort(array, storeIndex+1, end);
		}
	}
	

	
	public static void swap(int[] array, int i, int j)
	{
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}